package main

import "fmt"

/**
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

给定一个只包含(){}[]字符的字符串，判定该字符串是否按正确顺序闭合

分析: 这种问题通常使用栈解决比较方便
http://bangbingsyb.blogspot.com/2014/11/leetcode-valid-parentheses.html


*/

func isValid(s string) bool {
	var stack []rune

	for _, v := range s {
		//左半边入栈
		if v == '{' || v == '[' || v == '(' {
			stack = append(stack, v)
		}

		//右半边出栈
		if v == '}' || v == ']' || v == ')' {
			l := len(stack)
			if l == 0 {
				return false
			}

			if (v == '}' && stack[l-1] == '{') || (v == ']' && stack[l-1] == '[') || (v == ')' && stack[l-1] == '(') {
				stack = stack[:l-1]
			} else {
				return false
			}
		}
	}

	//最后判断栈是否为空
	if len(stack) == 0 {
		return true
	} else {
		return false
	}
}

/** 完全构造一个栈
type stack struct {
	data []byte
}

func (s *stack) pop() byte {
	ret := s.data[len(s.data)-1]
	s.data = s.data[0 : len(s.data)-1]
	return ret
}

func (s *stack) push(e byte) {
	s.data = append(s.data, e)
}

func (s *stack) top() byte {
	if len(s.data) > 0 {
		return s.data[len(s.data)-1]
	} else {
		return ' '
	}
}

func (s *stack) isempty() bool {
	if len(s.data) > 0 {
		return false
	} else {
		return true
	}
}

func isValid(str string) bool {
	if len(str) == 0 {
		return true
	}

	length := len(str)
	var s stack
	for i := 0; i < length; i++ {
		c := str[i]

		if c == '{' || c == '[' || c == '(' {
			s.push(c)
		} else if c == '}' && s.top() == '{' {
			s.pop()
		} else if c == ']' && s.top() == '[' {
			s.pop()
		} else if c == ')' && s.top() == '(' {
			s.pop()
		} else {
			return false
		}
	}

	return s.isempty()
}

*/

func main() {
	str := "]"
	if isValid(str) {
		fmt.Print("success")
	} else {
		fmt.Print("fail")
	}
}
